#include "sort.h"

/*  直接插入排序    */
// 时间复杂度分析：
// 最坏的情况：全逆序 —— O(N^2)
// 最好的情况：接近有序 —— O(N)
// 所以插入排序还是挺有用的，当我们已知有要排序的数组已经接近于有序了，用插排效率挺高的。

void InsertSort(int *a, int n)
{
    int i = 0;
    for (i = 0; i < n - 1; i++) // 执行 n-1轮
    {
        int end = i;
        int tmp = a[end + 1]; // 先把当前轮的数组的最后一个数存起来。
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end]; // 往后挪动
                --end;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}